Feature #3: Balloon Splash

Description#

We have to develop the game named Balloon Splash. Assume that there are multiple colored balloons, and we have to shoot a column of balloons of the same color. We can only splash k consecutive balloons of the same color. Once a set of k consecutive balloons is splashed, any balloons above it will fall to replace them. We will keep shooting until it is not possible to shoot k consecutive balloons of the same color. In the end, there will not be any k consecutive balloons left. For this problem, our input will be in the form of the English alphabet. Each letter will represent a unique colored balloon.

Let’s go through the following illustration to understand this problem:

Solution#

We are given a string str and an integer k, where the k consecutive letters that are identical can be eliminated from the string str. After removing the k consecutive occurrences of the same letter, we have to concatenate the remaining substrings together.

Here is how we will implement this feature:

• We will use a stack to maintain the count of adjacent duplicates.

• If the current character is the same as the previous one, we will increment the count on the top of the stack. Otherwise, we will push 1 along with the character to the stack.

• Next, we will check if the count on the top of the stack reaches k, and then perform the pop operation.

• We will iterate on the given string str until we reach the last character of the string.

Let’s see the following illustrations to understand this solution.

At the left, the given set of balloons is shown. Then, consecutive sets of 3 identical balloons are splashed repeatedly from left to right

Let’s look at the solution code below:

Complexity measures#

Time complexity#

We will iterate over all the $n$ characters of the given string exactly once. For each character, we will perform $O(1)$ operations. Therefore, the time complexity will be $O(n)$ in the worst-case scenario.

Space complexity#

The space complexity will be $O(n)$ in the worst-case scenario, when the stack will contain all the characters with their size.